package inner_sort

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/25 21:21
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 归并排序
 * */
type MergeSort struct {
	FromHighToLow bool // true表示从高到低排序,默认 false 表示从低到高排序
}

func NewMergeSort(options ...C.Options) *BucketSort {
	opt := C.NewOptions(options...)
	return &BucketSort{
		FromHighToLow: opt.FromHighToLow,
	}
}

func (m *MergeSort) SortMethod(array []int) {
	if len(array) < 2 {
		return
	}
	tempArr := make([]int, len(array)) // 辅助数组
	m.sort(array, tempArr, 0, len(array)-1)
}

func (m *MergeSort) sort(array, tempArr []int, left, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	m.sort(array, tempArr, left, mid)
	m.sort(array, tempArr, mid+1, right)
	m.merge(array, tempArr, left, mid, right)
}

func (m *MergeSort) merge(array, tempArr []int, left, mid, right int) {
	l := left
	r := mid + 1
	tempCur := left
	for l <= mid && r <= right {
		if array[l] < array[r] {
			tempArr[tempCur] = array[l]
			l++
		} else {
			tempArr[tempCur] = array[r]
			r++
		}
		tempCur++
	}
	for l <= mid {
		tempArr[tempCur] = array[l]
		l++
		tempCur++
	}
	for r <= right {
		tempArr[tempCur] = array[r]
		r++
		tempCur++
	}
	// HomeSort
	for i := left; i <= right; i++ {
		array[i] = tempArr[i]
	}
}

func (m *MergeSort) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "MergeSort",
			NameCn: "内部排序:归并排序",
			ParamsDesc: map[string]string{
				"fromHighToLow": "true表示从高到低排序, 默认 false 表示从低到高排序",
			},
			Example: map[int]string{
				1: "输入[1,3,2],跳用SortMethod方法进行排序后，输出[1,2,3]",
			},
		},
	}
}
